package q1377_frogPosition;

public class Solution {
    /*
    题目条件 只有1 - n个节点 要求在t秒后位于target上的概率
    首先明确 假设跳转了count次 只有count == t 或者 count < t && targetCount == 1 && target != 1 也就是count 小于 t 但是target是叶子节点
    才能够位于target上 否则返回0
     */
    public double frogPosition(int n, int[][] edges, int t, int target) {
        if (n == 1) return target == 1 && t >= 1 ? 1.0 : 0.0;
        // father记录各个节点的父节点
        int[] father = new int[n + 1];
        // sonNum记录每个节点有多少个子节点
        int[] sonNum = new int[n + 1];
        int targetCount = 0;
        for (int i = 0; i < n - 1; ++i) {
            /*
            这里判断父子节点的关系时出现问题 导致无法正常通过
             */
            if (edges[i][0] < edges[i][1]) {
                ++sonNum[edges[i][0]];
                father[edges[i][1]] = edges[i][0];
            }
            else {
                ++sonNum[edges[i][1]];
                father[edges[i][0]] = edges[i][1];
            }
            // 该判断用来检查target是否是一个叶子节点 如果是 那么count只能是1 否则就意味着这个节点被双向连接
            if (edges[i][0] == target || edges[i][1] == target) {
                ++targetCount;
            }
        }

        double probability = 1.0;
        int count = 0;
        int idx = target;
        while (father[idx] > 0) {
            probability /= sonNum[father[idx]];
            idx = father[idx];
            ++count;
        }
        if ((count < t && targetCount == 1 && target != 1) || count == t) {
            return probability;
        }
        return 0.0;

    }
}
